#include <iostream>
using namespace std;

struct Node
{
	int data;
	Node* pNext;
};

void insertAtB(Node* &head, int t);
void insertAtB(Node* &head, Node* tmp);
void deleteAll(Node* &head);
void displayAll(Node* head);

int deleteFirstNode(Node* &head);

//1: successful, -1:unsuccessful
int deleteNodek(Node* &head, int k);

int insertKAfterX(Node* &head, int k, int x);

int main()
{
	Node* head=NULL;

	insertAtB(head, 5);
	insertAtB(head, 4);
	insertAtB(head, 3);
	insertAtB(head, 2);
	insertAtB(head, 1);

	displayAll(head);

	deleteNodek(head, 3);
	displayAll(head);

	deleteNodek(head, 5);
	displayAll(head);

	deleteNodek(head, 1);
	displayAll(head);

	deleteAll(head);
	return 0;
}

void insertAtB(Node* & head, int t)
{
		Node* tmp = new Node;
		tmp->data = t;
		tmp->pNext = head;
		head = tmp;
}

void insertAtB(Node* &head, Node* tmp)
{
	tmp->pNext = head;
	head = tmp;
}

void deleteAll(Node* &head)
{
	Node* tmp = head;
	while (head!=NULL)
	{
		head = head->pNext;
		delete tmp;
		tmp = head;
	}
}

void displayAll(Node* head)
{
	Node* cur = head;
	while (cur)
	{
		cout << cur->data << " ";
		cur = cur->pNext;
	}
	cout << endl;
}

int deleteNodek(Node* &head, int k)
{
	if (head == NULL)
		return -1;
	if (head->data == k) //at the beginning
		return deleteFirstNode(head);
	else
	{
		Node* cur = head;
		while (cur->pNext != NULL && cur->pNext->data != k)
			cur = cur->pNext;
		if (cur->pNext != NULL) //cur nam tai Node truoc K
		{
			Node* tmp = cur->pNext;
			cur->pNext = tmp->pNext;
			delete tmp;
			return 1;
		}
	}
}

int deleteFirstNode(Node* &head)
{
	if (head == NULL)
		return -1;
	Node* tmp = head;
	head = head->pNext;
	delete tmp;
	return 1;
}
int insertKAfterX(Node* &head, int k, int x)
{
	Node *cur=head;
	if(head==NULL)
	{
		head = new Node;
		head->data=k;
		head->pNext=NULL;
		return 1;
	}
	
	// cur->data == x || cur->pNext == NULL
	while(cur->pNext!=NULL && cur->data!=x)
		cur=cur->pNext;

	Node *cur2=cur->pNext;
	cur->pNext=new Node;
	cur=cur->pNext;
	cur->data=k;
	cur->pNext=cur2;

	return 1;

}